package priotityqueue;
import java.util.*;

class KthLargest {

    PriorityQueue<Integer> heap;
    int topK;

    public KthLargest(int k, int[] nums) {
        topK = k;
        heap = new PriorityQueue<>((a, b) -> a - b);
        for(int x : nums){
            heap.offer(x);
            if(heap.size() > topK){
                heap.poll();
            }
        }
    }

    public int add(int val) {
        heap.offer(val);
        if(heap.size() > topK){
            heap.poll();
        }
        return heap.peek();
    }
}

public class Solution {

    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        for(int x : stones){
            heap.offer(x);
        }

        while(heap.size() > 1){
            int a = heap.poll();
            int b = heap.poll();
            if(a != b){
                heap.offer(a - b);
            }
        }
        return heap.isEmpty() ? 0: heap.peek();
    }

//    public List<String> topKFrequent(String[] words, int k) {
//
//        Map<String, Integer> hash = new HashMap<>();
//        for(String word : words){
//            hash.put(word, hash.getOrDefault(word, 0) + 1);
//        }
//
//        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
//            if(a.getValue().equals(b.getValue())){
//                return b.getKey().compareTo(a.getKey());
//            }
//            return a.getValue() - b.getValue();
//        });
//
//        for(Map.Entry<String, Integer> e : hash.entrySet()){
//            heap.offer(new Pair<>(e.getKey(), e.getValue()));
//            if(heap.size() > k){
//                heap.poll();
//            }
//        }
//
//        List<String> ret = new ArrayList<>();
//        while(!heap.isEmpty()){
//            ret.add(heap.poll().getKey());
//        }
//
//        Collections.reverse(ret);
//        return ret;
//    }
}
